
//问题 A: 【数据结构2-9】单向有序链表按值插入（C版本）
//时间限制: 1 Sec  内存限制: 128 MB
//提交: 514  解决: 181
//[提交][状态][论坛]
//题目描述
//原由链表结点的数据是按照从小到大排序的，输入一个新的数据，插入到链表中，使它仍然有序
//
//输入
//第一行输入一组正整数（ 其他以从小到大的序列给出）-1结束，创建链表
//
//第二行输入要插入的整数
//
//输出
//插入后有序的序列
//样例输入
//1 3 4 5 7 9 -1
//6
//样例输出
//1 3 4 5 6 7 9 

#include <stdio.h>
#include <stdlib.h>
struct node {
	int data;
	struct node *next;
};
struct node * insertlinkby_elem(struct node *head, int elem);
void destroy(struct node* head);
struct node* creatlink();
void traverse(struct node* head);

int main() {
	int  c;
	struct node *head;
	head=creatlink();   //用尾插法创建链表
	scanf("%d",&c);
	head=insertlinkby_elem(head,c);
	traverse(head);
	destroy(head);
	return 0;
}

struct node* creatlink() { //尾插法创建链表
	struct node* head=NULL;
	int c;
	struct node  *p,*q;

	while(1) {
		scanf("%d",&c);
		if(c==-1) break;

		//申请结点空间
		p = (struct node *) malloc (sizeof(struct node));

		//初始化结点数据域
		p->next = NULL;
		p->data = c;
		if(head == NULL) {

			head = p;
			q=p;    //设置尾指针
		} else {
			q->next = p; //挂入链尾
			q=p;  //设置尾指针
		}
	}
	return head;
}

void traverse(struct node* head) {
	struct node *p=head;
	while( p!=NULL) {                  //如果p指向的结点不是空结点
		printf("%d ",p->data);   //则输出所指向的结点的数据域
		p=p->next;                       //让p指向下一个结点
	}
}


void destroy(struct node* head){
	struct node *p;
	while(head!=NULL){
		p=head;
		head=head->next;
		free(p);
	} 
	
}
struct node * insertlinkby_elem(struct node *head, int elem){
	struct node *p,*q,*t;
	t=head;
	int flag=0;
	//头插
	if(elem<t->data){
		flag=1;
		p=(struct node*) malloc (sizeof(struct node));
		p->data=elem;
		p->next=head;
		head=p;
	}else{
		//查找插入的位置 
		while(t->next!=NULL){
			if(elem<t->next->data){
				flag=1;
				p=(struct node*) malloc (sizeof(struct node));
				p->data=elem;
				p->next=t->next;
				t->next=p;
				break;
			}
			t=t->next;
		}
	}
    //插到最后
	if(flag==0){
		t=head;
		p=(struct node*) malloc (sizeof(struct node));
		p->data=elem;
		p->next=NULL;
		while(t->next!=NULL){
			t=t->next;
		}
		t->next=p;
	}
	
	
	return head;
}